package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-05-14 11:36
 */
public class CB945使数组唯一的最小增量 {

    public static void main(String[] args) {

        int[] nums = {14, 4, 5, 14, 13, 14, 10, 17, 2, 12, 2, 14, 7, 13, 14, 13, 4, 16, 4, 10};
        System.out.println(minIncrementForUnique(nums));
    }

    public static int minIncrementForUnique(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
        }
        boolean[] numFlag = new boolean[max + nums.length];
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (!numFlag[nums[i]]) {
                numFlag[nums[i]] = true;
            } else {
                list.add(nums[i]);
            }
        }
        if (list.size() == 0) {
            return 0;
        }

        list.sort(Comparator.naturalOrder());
        int total = 0;
        int right = list.get(0) + 1;
        //将剩下的重复元素 从小到大移动
        for (int i = 0; i < list.size(); i++) {
            int index = list.get(i);
            if (index > right) {
                right = index + 1;
            }
            while (numFlag[right]) {
                right++;
            }
            numFlag[right] = true;
            total += right - list.get(i);
        }
        return total;
    }
}
